package shardctrler

import (
	"math"
	"sort"
)

//
// Shard controler: assigns shards to replication groups.
//
// RPC interface:
// Join(servers) -- add a set of groups (gid -> server-list mapping).
// Leave(gids) -- delete a set of groups.
// Move(shard, gid) -- hand off one shard from current owner to gid.
// Query(num) -> fetch Config # num, or latest config if num==-1.
//
// A Config (configuration) describes a set of replica groups, and the
// replica group responsible for each shard. Configs are numbered. Config
// #0 is the initial configuration, with no groups and all shards
// assigned to group 0 (the invalid group).
//
// You will need to add fields to the RPC argument structs.
//

// The number of shards.
const NShards = 10

// A configuration -- an assignment of shards to groups.
// Please don't change this.
type Config struct {
	Num    int              // config number
	Shards [NShards]int     // shard -> gid
	Groups map[int][]string // gid -> servers[]

	CachedGid map[int][]string // gid -> cached_servers[]
}

const (
	OK                 = "OK"
	ErrNoKey           = "ErrNoKey"
	ErrWrongLeader     = "ErrWrongLeader"
	ErrHandleOpTimeOut = "ErrHandleOpTimeOut"
	ErrChanClosed      = "ErrChanClosed"
	ErrLeaderOutdated  = "ErrLeaderOutdated"
)

type Err string

type JoinArgs struct {
	Servers  map[int][]string // new GID -> servers mappings
	Seq      uint64
	ClientId int64
}

type JoinReply struct {
	WrongLeader bool
	Err         Err
}

type LeaveArgs struct {
	GIDs     []int
	Seq      uint64
	ClientId int64
}

type LeaveReply struct {
	WrongLeader bool
	Err         Err
}

type MoveArgs struct {
	Shard    int
	GID      int
	Seq      uint64
	ClientId int64
}

type MoveReply struct {
	WrongLeader bool
	Err         Err
}

type QueryArgs struct {
	Num      int // desired config number
	Seq      uint64
	ClientId int64
}

type QueryReply struct {
	WrongLeader bool
	Err         Err
	Config      Config
}

func (cf *Config) check_nil_map() {
	if cf.CachedGid == nil {
		cf.CachedGid = make(map[int][]string)
	}

	if cf.Groups == nil {
		cf.Groups = make(map[int][]string)
	}
}

func (cf *Config) add_cache(gid int, servers []string) {
	if cf.CachedGid == nil {
		cf.CachedGid = make(map[int][]string)
	}

	if _, exist := cf.Groups[gid]; !exist && len(cf.Groups) == NShards {
		cf.CachedGid[gid] = servers
	}
}

func (cf *Config) remove_cache(gids []int) {
	if cf.CachedGid == nil {
		cf.CachedGid = make(map[int][]string)
		return
	}

	for _, gid := range gids {
		delete(cf.CachedGid, gid)
	}
}

func (cf *Config) remove_group(gids []int) {
	for _, gid := range gids {
		delete(cf.Groups, gid)
	}
	for idx, gid := range cf.Shards {
		if _, exist := cf.Groups[gid]; !exist {
			cf.Shards[idx] = 0
		}
	}
}

func (cf *Config) move_cache() {
	if cf.CachedGid == nil {
		cf.CachedGid = make(map[int][]string)
		return
	}

	move_total := NShards - len(cf.Groups)

	move_idx := 0

	cache_gids := make([]int, 0, len(cf.CachedGid))
	for cache_key := range cf.CachedGid {
		cache_gids = append(cache_gids, cache_key)
	}

	sort.Ints(cache_gids) // 需要按照顺序移动到Groups

	for move_idx < move_total && move_idx < len(cache_gids) {
		move_key := cache_gids[move_idx]
		cf.Groups[move_key] = cf.CachedGid[move_key]
		delete(cf.CachedGid, move_key)

		move_idx++
	}
}

func deep_copy_map(oldConfig *Config, newConfig *Config) {
	oldConfig.check_nil_map()
	newConfig.check_nil_map()

	for gid, group := range oldConfig.Groups {
		newConfig.Groups[gid] = group
	}

	for gid, group := range oldConfig.CachedGid {
		newConfig.CachedGid[gid] = group
	}
}

func get_max_map_len_count(newConfig *Config) (map_shard_len map[int]int, max_map_gid_len int, max_map_gid_count int) {
	map_shard_len = make(map[int]int)

	max_map_gid_len = 0   // gid包含最多shard的数量
	max_map_gid_count = 0 // 含最多shard的数量的group的数量

	for _, gid := range newConfig.Shards {
		map_shard_len[gid]++
		if map_shard_len[gid] > max_map_gid_len {
			max_map_gid_len = map_shard_len[gid]
		}
	}

	for _, gid := range newConfig.Shards {
		if map_shard_len[gid] == max_map_gid_len {
			max_map_gid_count += 1
		}
	}
	return
}

func get_min_arr(newConfig *Config) (map_shard_min []int) {

	map_shard_min = make([]int, 0)

	map_shard_len := make(map[int]int)

	min_map_gid_len := math.MaxInt // gid包含最少shard的数量

	for _, gid := range newConfig.Shards {
		if _, exist := newConfig.Groups[gid]; exist {
			map_shard_len[gid]++
		}
	}

	// Groups中没有映射到的gid置为0
	for gid := range newConfig.Groups {
		if _, exist := map_shard_len[gid]; !exist {
			map_shard_len[gid] = 0
		}
	}

	for _, count := range map_shard_len {
		min_map_gid_len = int(math.Min(float64(count), float64(min_map_gid_len)))
	}

	for gid, count := range map_shard_len {
		if count == min_map_gid_len {
			map_shard_min = append(map_shard_min, gid)
		}
	}
	// 必须确保有序
	sort.Ints(map_shard_min)

	return
}
